#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100

typedef struct {
    int n;                        // 图中顶点的数量
    int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
} Graph;

typedef struct {
    int items[MAX_VERTICES];
    int front, rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = -1;
}

// 队列是否为空
int isEmpty(Queue *q) {
    return q->front > q->rear;
}

// 入队
void enqueue(Queue *q, int item) {
    q->items[++q->rear] = item;
}

// 出队
int dequeue(Queue *q) {
    if (!isEmpty(q)) {
        return q->items[q->front++];
    }
    return -1;
}

void initGraph(Graph *g, int numVertices) {
    g->n = numVertices;
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

void addEdge(Graph *g, int u, int v) {
    g->adjMatrix[u][v] = 1;
    g->adjMatrix[v][u] = 1;
}

// BFS 实现
void BFS(Graph *g, int startVertex) {
    int visited[MAX_VERTICES] = {0};
    Queue q;
    initQueue(&q);

    visited[startVertex] = 1; // 标记起始顶点为已访问
    printf("Visited %d\n", startVertex);
    enqueue(&q, startVertex);

    while (!isEmpty(&q)) {
        int currentVertex = dequeue(&q);

        for (int i = 0; i < g->n; i++) {
            if (g->adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                printf("Visited %d\n", i);
                enqueue(&q, i);
            }
        }
    }
}

int main() {
    Graph g;
    initGraph(&g, 4);
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 2);
    addEdge(&g, 2, 3);

    printf("BFS starting from vertex 0:\n");
    BFS(&g, 0);

    return 0;
}
